// 方式三，中心扩展
// 时间：124ms
function longestPalindrome(s) {
  const len = s.length;
  const next = getNext(s);
  let targtI = 0;
  let targetJ = 0;
  let maxLen = 1;
  if (len === 1) return s;
  //循环对比，并 跳过连续相同的字符串
  for (let i = 0; i < len; i += next[i]) {
    // 获取最长的回文起始坐标
    let [start, end] = getMaxLenPos(i, i + next[i] - 1, len, s);
    let count = end - start + 1;
    // // 记录当前最大的回文长度及坐标
    if (count > maxLen) {
      targtI = start;
      targetJ = end;
      maxLen = count;
    }
  }
  return s.substring(targtI, targetJ + 1);

  function getNext(s) {
    const next = new Array(len).fill(1);
    // 计算连续重复的字符串
    for (let i = len - 2; i >= 0; i--) {
      if (s[i] === s[i + 1]) {
        next[i] = next[i + 1] + 1;
      }
    }
    return next;
  }
  // 获取当前中心位置的回文坐标，两边扩散
  function getMaxLenPos(i, j, len, s) {
    while (i > 0 && j < len && s[i - 1] === s[j + 1]) {
      i--;
      j++;
    }
    return [i, j];
  }
}

console.log(longestPalindrome("abccba"));
